package cn.tedu.java.thread;

import java.util.NoSuchElementException;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 基于双向链表构建一个阻塞式队列
 * 1)数据的存储结构：双向链表
 * 2)数据的存取算法：FIFO(先进先出)
 */
class SimpleLinkedBlockingQueue{//ArrayList,LinkedList

     /**链表中的第一个节点(头节点)*/
     private Node first;
     /**链表中的最后一个节点(尾节点)*/
     private Node last;
     /**记录有效元素的个数*/
     private int size;

      /**构建链表中节点的类型*/
     private static class Node{
          /**前驱指针(用于指向上一个节点)*/
          Node pre;
          /**基于此属性存储具体数据*/
          Object element;
          /**后继指针(用于指向下一个节点)*/
          Node next;
          public Node(Node pre,Object element,Node next){
              this.pre=pre;
              this.element=element;
              this.next=next;
          }
      }
      /**定义容器的容量大小*/
      private int capacity;
      public SimpleLinkedBlockingQueue(int capacity){
         this.capacity=capacity;
      }
     //Java中可以基于这个API执行加锁操作(类似synchronized,只是在api的维度进行加锁)
     private ReentrantLock reentrantLock=new ReentrantLock();
     //构建通讯条件对象
     private Condition producerCondition=reentrantLock.newCondition();
     private Condition consumerCondition=reentrantLock.newCondition();

    /**
     * 在链表的尾部添加元素
     * @param element
     */
      public  void addLast(Object element)throws InterruptedException{
          reentrantLock.lock();//加锁
          try {
              //容器满了则等待
              while(size==capacity)producerCondition.await();
              //1.获取尾部节点
              Node tail = last;
              //2.创建新节点，并且让新节点的上一个节点为原先链表的尾节点
              Node newNode = new Node(tail, element, null);
              //3.更新最后一个节点(设置新节点为最后一个节点)，假如没有尾节点，这个新节点即是头节点也是尾节点
              last = newNode;
              if (tail == null) {
                  first = newNode;
              } else {
                  tail.next = newNode;
              }
              //4.更新有效元素个数。
              size++;
              //通知消费者线程取数据
              consumerCondition.signalAll();
          }finally{
              reentrantLock.unlock();
          }
      }

    /**
     * 在链表的头部移除元素
     * @return 被移除的元素
     */
      public  Object removeFirst()throws InterruptedException{
          reentrantLock.lock();
          try {
              //空了则阻塞
              while(size==0)consumerCondition.await();
              //1.获取第一个节点
              Node head = first;
              //if(head==null)throw new NoSuchElementException();
              //2.获取头节点元素
              Object element = head.element;
              //3.设置新的头节点
              Node newHead = head.next;
              first = newHead;
              if (newHead == null) {
                  last = null;
              } else {
                  newHead.pre = null;//没有上一个节点的节点是头节点
              }
              //4.释放原先的header节点
              head.element = null;
              head.pre = null;
              head.next = null;
              //5.有效元素个数减一
              size--;
              producerCondition.signalAll();
              return element;
          }finally{
              reentrantLock.unlock();
          }

      }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder("[");
        Node node=first;
        while(node!=null){
            sb.append(node.element).append(",");
            node=node.next;
        }
        if(sb.length()>1)sb.deleteCharAt(sb.length()-1);
        sb.append("]");
        return sb.toString();
    }
}

public class SimpleLinkedBlockingQueueTests {
    public static void main(String[] args) throws InterruptedException{
          SimpleLinkedBlockingQueue queue=
                  new SimpleLinkedBlockingQueue(3);
          queue.addLast("A");//head
          queue.addLast("B");
          queue.addLast("C");//tail
          System.out.println(queue);
         // queue.addLast("D");
          System.out.println(queue.removeFirst());//A
          System.out.println(queue.removeFirst());//B
          System.out.println(queue.removeFirst());//C
          System.out.println(queue);
          System.out.println(queue.removeFirst());//C
    }
}
